//
// Created by francklinson on 2021/8/24 AT 22:08.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <set>

using namespace std;

class Solution {
public:
    int robotSim(vector<int> &commands, vector<vector<int>> &obstacles) {
        // 北 东 南 西
        int dx[4]{0, 1, 0, -1};
        int dy[4]{1, 0, -1, 0};
        // 初始位置和方向
        int x = 0, y = 0, dir = 0;
        // 把障碍物的坐标存成string，放在set中
        unordered_set<string> obstaclesSet;
        for (auto obs:obstacles) {
            string pos = to_string(obs[0]) + ',' + to_string(obs[1]);
            obstaclesSet.insert(pos);
        }
        int ans = 0;
        for (auto &cmd:commands) {
            if (cmd == -2) {
                dir = (dir + 3) % 4;
            } else if (cmd == -1) {
                dir = (dir + 1) % 4;
            } else {
                for (int i = 0; i < cmd; ++i) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    // 没有被阻碍
                    if (!obstaclesSet.count(to_string(nx) + ',' + to_string(ny))) {
                        x = nx;
                        y = ny;
                        ans = max(ans, x * x + y * y);
                    } else
                        break;

                }
            }
        }
        return ans;
    }
};

class Solution2 {
public:
    int robotSim(vector<int> &commands, vector<vector<int>> &obstacles) {
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};

        int x = 0;
        int y = 0;
        int ans = 0;
        int direction = 0;

        // 存储障碍物坐标  用set+pair更快些
        set<pair<int, int>> obstaclesSet;
        for (int i = 0; i < obstacles.size(); i++) {
            obstaclesSet.insert({obstacles[i][0], obstacles[i][1]});
        }

        for (int i = 0; i < commands.size(); i++) {
            if (commands[i] == LEFT_FLAG) {
                direction = (direction + 3) % 4;
            } else if (commands[i] == RIGHT_FLAG) {
                direction = (direction + 1) % 4;
            } else {
                for (int j = 0; j < commands[i]; j++) {
                    int tmpX = x + dx[direction];
                    int tmpY = y + dy[direction];
                    if (obstaclesSet.find({tmpX, tmpY}) == obstaclesSet.end()) {
                        x = tmpX;
                        y = tmpY;
                        ans = max(ans, x * x + y * y);
                    }
                }
            }
        }

        return ans;
    }

private:
    static const int LEFT_FLAG = -2;
    static const int RIGHT_FLAG = -1;
};

int main() {
    Solution2 solution;
    vector<int> commands{4, -1, 4, -2, 4};
    vector<vector<int>> obstacles{{2, 4}};
    cout << solution.robotSim(commands, obstacles) << endl;
    return 0;
}

